Curso Académico:
2019/20
30214 - Teoría de la computación
Información del Plan Docente
Año académico:
2019/20
Asignatura:
30214 - Teoría de la computación
Centro académico:
110 - Escuela de Ingeniería y Arquitectura
326 - Escuela Universitaria Politécnica de Teruel
Titulación:
439 - Graduado en Ingeniería Informática
443 - Graduado en Ingeniería Informática
Créditos:
6.0
Curso:
2
Periodo de impartición:
Primer semestre
Clase de asignatura:
Formación básica
Materia:
Materia básica de grado
1.1. Objetivos de la asignatura
La asignatura y sus resultados previstos responden a los siguientes planteamientos y objetivos:
Los objetivos de la asignatura son fundamentalmente de cuatro tipos:
- Capacitar al estudiante para que pueda abstraer problemas a resolver mediante un computador.
- Conocer los modelos de cálculo básicos en los que se basan los computadores actuales e identificar el más adaptado a cada problema.
- Asimilar paradigmas de problemas bien estudiados en el contexto de la informática para que pueda reducirlos o adaptarlos a los problemas que se le planteen.
- Conocer las capacidades y limitaciones de la resolución automática de problemas y evaluar los recursos necesarios para ello.
1.2. Contexto y sentido de la asignatura en la titulación
La Teoría de la Computación es una asignatura de Formación Básica impartida en el segundo curso de la titulación. Esta particular ubicación temporal permite que los estudiantes puedan aplicar en todas las asignaturas de la titulación los conocimientos adquiridos en esta asignatura: decidibilidad, teoría de lenguajes y complejidad. Estas herramientas formarán parte del conjunto de habilidades y métodos fundamentales que el ingeniero informático aplicará en su trabajo.
1.3. Recomendaciones para cursar la asignatura
Es conveniente que el alumno haya cursado las asignaturas de Programación I (1er Cuatrimestre) y Matemática Discreta (2º Cuatrimestre).
2. Competencias y resultados de aprendizaje
2.1. Competencias
Al superar la asignatura, el estudiante será más competente para...
Resolver problemas y tomar decisiones con iniciativa, creatividad y razonamiento crítico.
Comunicar y transmitir conocimientos, habilidades y destrezas en castellano.
Usar las técnicas, habilidades y herramientas de la Ingeniería necesarias para la práctica de la misma.
Aprender de forma continuada y desarrollar estrategias de aprendizaje autónomo.
Aplicar las tecnologías de la información y las comunicaciones en la Ingeniería.
Comprender y dominar los conceptos básicos de matemática discreta, lógica, algoritmia y complejidad computacional, y su aplicación para la resolución de problemas propios de la ingeniería.
Usar ordenadores, sistemas operativos, bases de datos y programas informáticos con aplicación en ingeniería.
2.2. Resultados de aprendizaje
El estudiante, para superar esta asignatura, deberá demostrar los siguientes resultados...
Conoce los modelos de cálculo básicos.
Encuentra el modelo de cálculo más simple para cada problema.
Descarta soluciones incorrectas por ser demasiado simples para problemas dados.
Describe adecuadamente los procesos de cálculo.
Aplica los formalismos de la teoría de lenguajes en la resolución de problemas.
Transforma enunciados informales en enunciados formales y viceversa.
Conoce las limitaciones de la resolución automática de problemas.
Identifica problemas irresolubles básicos como el problema de parada o el de detección de virus.
Analiza el coste en tiempo y memoria de un algoritmo.
Identifica problemas que requieren demasiados recursos de cálculo.
2.3. Importancia de los resultados de aprendizaje
El conjunto de los resultados de aprendizaje se puede resumir diciendo que el alumno será capaz de abstraer un problema a resolver mediante un computador identificando el modelo de cálculo más adecuado, reduciéndolo a problemas conocidos e identificando las limitaciones de dicha resolución y los recursos necesarios para ella. Haber aprendido a hacerlo bien y con eficiencia es de vital importancia en el contexto de unos estudios de Ingeniería Informática de los que uno de sus pilares es la resolución de problemas.
3.1. Tipo de pruebas y su valor sobre la nota final y criterios de evaluación para cada prueba
El estudiante deberá demostrar que ha alcanzado los resultados de aprendizaje previstos mediante las siguientes actividades de evaluacion
En la Escuela de Ingeniería y Arquitectura de Zaragoza:
Trabajo de laboratorio (30%). Por una parte, se evaluará el guión previo donde el estudiante deberá haber identificado las necesidades de información para resolver los problemas planteados y su utilización en la resolución. También se valorará la capacidad crítica a la hora de seleccionar alternativas y el grado de justificación de la solución alcanzada.
Se evaluará, por otra parte, la soltura en el manejo del computador para resolver problemas. También se evaluarán las soluciones implementadas para cada uno de los ejercicios planteados para las sesiones de prácticas, atendiendo a la calidad de los procedimientos y estrategias de resolución eficiente en el computador.
Prueba escrita (70%) en la que se plantearán cuestiones y/o problemas del ámbito de la Ingeniería Informática a resolver mediante un computador, de tipología y nivel de complejidad similar al utilizado durante el curso. Se valorará la calidad y claridad de la estrategia de resolución, así como su eficiencia.
Se requiere una nota mínima de 4 puntos sobre un total de 10 en la prueba escrita para aprobar la asignatura. Si se obtiene esta nota mínima, entonces la prueba escrita pondera un 70% en la nota de la asignatura y, si no se alcanza este mínimo, entonces la calificación en la asignatura es la de la prueba escrita.
En la Escuela Universitaria Politécnica de Teruel:
La nota final de la asignatura en la convocatoria ordinaria se divide de la siguiente forma:
Examen escrito. 70% de la nota final. Constará de una parte de teoría y otra de problemas. A mitad de asignatura habrá una prueba parcial que permitirá "adelantar" nota de cara al examen.
Trabajo teórico. 5% de la nota final. Consistirá en un trabajo de temática a definir durante el curso que tratará sobre alguno de los temas de la asignatura.
Prácticas. 25% de la nota final. Habrá varias prácticas entregables a lo largo del curso.
Se requiere una nota mínima de 4 puntos sobre un total de 10 en la prueba escrita para aprobar la asignatura. Si se obtiene esta nota mínima, entonces se realizará la ponderación antes indicada. Si no se alcanza este mínimo, entonces la calificación en la asignatura es la de la prueba escrita.
En cuanto a la convocatoria extraordinaria (septiembre), la nota final será la nota del examen extraordinario, teniendo en cuenta que ese examen tendrá una parte de teoría y problemas que valdrá el 75% de la nota total y una de prácticas que valdrá el 25%. No se mantendrán para septiembre las notas del parcial ni del trabajo.
Organización de las actividades de evaluación
El alumno superará la asignatura mediante la realización de las actividades enumeradas en el apartado anterior y con las ponderaciones relativas allí señaladas. La evaluación global se desglosará en dos partes correspondientes a dichas actividades y su fecha de realización se especificará con suficiente antelación por el centro. Los alumnos que hubieran superado la actividad 1) durante el curso también podrán presentarse a subir nota en las fechas de la evaluación global.
4. Metodología, actividades de aprendizaje, programa y recursos
4.1. Presentación metodológica general
El proceso de aprendizaje que se ha diseñado para esta asignatura se basa en lo siguiente:
- La presentación de los contenidos de la asignatura en clases magistrales por parte de los profesores.
- La resolución de problemas planteados en clase.
- El estudio personal de la asignatura por parte de los alumnos.
- El desarrollo de prácticas por parte de los alumnos, guiadas por los profesores, que desarrollan los conocimientos teóricos.
- La resolución de problemas sencillos de dificultad creciente propuestos por los profesores.
Se debe tener en cuenta que la asignatura tiene una orientación tanto teórica como práctica. Por ello, el proceso de aprendizaje pone énfasis tanto en la asistencia del alumno a las clases magistrales, como en la realización de prácticas en laboratorio, en la resolución de problemas sencillos de dificultad creciente, y en el estudio individualizado.
4.2. Actividades de aprendizaje
El programa que se ofrece al estudiante para ayudarle a lograr los resultados previstos comprende las siguientes actividades...
En las clases impartidas en el aula se desarrollará el programa de la asignatura.
En las clases de problemas se resolverán problemas de aplicación de los conceptos y técnicas presentadas en el programa de la asignatura.
Las sesiones de prácticas de desarrollan en un laboratorio informático.
4.3. Programa
El programa de esta asignatura se organiza alrededor de tres pilares básicos: (1) Teoría de lenguajes formales , con énfasis en los lenguajes regulares y los independientes de contexto; (2) Fundamentos de Computabilidad, para acotar qué problemas pueden ser resueltos algorítmicamente; (3) Fundamentos de Complejidad Algorítmica, para definir qué es eficiencia de una solución algorítmica y los recursos que necesita un algoritmo.
Tema 0: Preliminares
Preliminares matemáticos: conjuntos, funciones, relaciones, inducción.
Definición de alfabeto y lenguaje.
Tema 1: Lenguajes Regulares
Expresiones regulares y lenguajes regulares.
Autómatas finitos deterministas (AFD) y no deterministas (AFnD)
Equivalencia entre AFD y AFnD.
Propiedades de los lenguajes regulares. Lema de bombeo
Tema 2: Lenguajes Independientes de Contexto
Gramáticas y lenguajes independientes del contexto.
Autómatas de pila.
Simplificación de gramáticas.
Propiedades de los lenguajes independientes del contexto. Lema de bombeo
Tema 3: Computabilidad
Máquinas de Turing.
Lenguajes y Máquinas de Turing. Tesis de Church-Turing.
Decidibilidad. Problemas no decidibles.
Tema 4: Complejidad
Clases de lenguajes P y EXP.
Clases de lenguajes NP y NP-completo.
Los conceptos, métodos y herramientas de los apartados anteriores se ilustrarán a través de ejemplos, lo más realistas posibles, dentro de los ámbitos de: seguridad informática, criptografía, procesamiento de lenguaje natural y compresión de la información.
4.4. Planificación de las actividades de aprendizaje y calendario de fechas clave
Calendario de sesiones presenciales y presentación de trabajos
El calendario de la asignatura estará definido por el centro en el calendario académico del curso correspondiente.
Trabajo del estudiante
La dedicación del estudiante para alcanzar los resultados de aprendizaje en esta asignatura se estima en 150 horas distribuidas del siguiente modo:
En la Escuela de Ingeniería y Arquitectura de Zaragoza:
- 56 horas, aproximadamente, de actividades presenciales (clases teóricas, de problemas y prácticas en laboratorio)
- 40 horas de trabajo en equipo
- 51 horas de estudio personal efectivo (estudio de apuntes y textos, resolución de problemas, preparación clases y prácticas)
- 3 horas de examen final escrito
En la Escuela Universitaria Politécnica de Teruel:
- 60 horas de actividades presenciales (clases teóricas, de problemas y prácticas en laboratorio)
- 30 horas de trabajo en equipo
- 55 horas de estudio personal efectivo (estudio de apuntes y textos, resolución de problemas, preparación clases y prácticas)
- 5 horas de actividades de evaluación
El calendario de exámenes y las fechas de entrega de trabajos de evaluación se anunciarán con suficiente antelación.
En la Escuela de Ingeniería y Arquitectura del Campus Rio Ebro:
En la Escuela Universitaria Politécnica del Campus de Teruel